package main

import "fmt"

/*
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
*/

/*
还记得斐波那契数列吗？这也差不多呢！
无论你站在哪个台阶，能到达这个台阶的方式只有两种：从n-1来，从n-2来；
那么，到达n的方式就有到达n-1的方式和到达n-2的方式的总和。

动态规划表达式：

	f(n)：到达台阶n方式数

动态规划方程：

	f(n)=f(n-1)+f(n-2) n>2
	f(1)=1
	f(2)=2
*/
func climbStairs1(n int) int {
	if n < 3 {
		return n
	}
	f := make([]int, n+1)
	f[1] = 1
	f[2] = 2
	for i := 3; i <= n; i++ {
		f[i] = f[i-1] + f[i-2]
	}
	return f[n]
}

/*
优化：

	和斐波那契数列一样，只需要记录前两步的就够了
*/
func climbStairs2(n int) int {
	if n < 3 {
		return n
	}
	f := [2]int{}
	f[2&1] = 2
	f[1&1] = 1
	for i := 3; i <= n; i++ {
		f[i&1] = f[0] + f[1]
	}
	return f[n&1]
}

func main() {
	n := 4
	fmt.Println(climbStairs1(n))
	fmt.Println(climbStairs2(n))
}
